import numpy as np
import os
import enum
import random
import time
import copy
from anytree import Node,search,LevelOrderIter,RenderTree

class GameResult(enum.Enum):
    loss = 1
    draw = 2
    win = 3

class GameState(enum.Enum):
    waiting=0 #初始状态
    running=1 #游戏开始了
    over=2 #胜负已分

player_x=1  #画叉方
player_o=-1 #画圈方
max_depth=4 #井字棋最多才9格，深度为10的话就是全部都搜索到了
maxValue=1
minValue=-1

class Board: #棋盘
    def __init__(self):
        self.board=np.zeros((3,3))
    def printBoard(self):
        for i in range(3):
            line='|'
            ele=[]
            for j in range(3):
                if self.board[i,j]==-1:
                    ele.append('_O_')
                elif self.board[i,j]==1:
                    ele.append('_X_')
                else:
                    ele.append('___')
            print(line.join(ele))



class Game:
    def __init__(self, board, player=player_x,game_state=GameState.waiting): #1表示X，-1表示O
        self.board=board
        self.player=player
        self.winner=None
        self.state=game_state
        self.bot1=None
        self.bot2=None
        self.last_move=None  #蒙特卡洛方法时用到


    def getResult(self):
        for i in range(3):
            if self.board.board.item((i,0))==self.board.board.item((i,1))==self.board.board.item((i,2))!=0: #竖
                result=(0,self.board.board.item((i,0))) #0表示有胜负
                self.winner=result[1]
                self.state=GameState.over
                return result
            if self.board.board.item((0,i))==self.board.board.item((1,i))==self.board.board.item((2,i))!=0: #横
                result=(0,self.board.board.item((0,i)))
                self.winner=result[1]
                self.state=GameState.over
                return result
        if self.board.board.item((0,0))==self.board.board.item((1,1))==self.board.board.item((2,2))!=0: #左上->右下
            result=(0,self.board.board.item((0,0)))
            self.winner=result[1]
            self.state=GameState.over
            return result
        elif self.board.board.item((0,2))==self.board.board.item((1,1))==self.board.board.item((2,0))!=0: #右上->左下
            result=(0,self.board.board.item((0,2)))
            self.winner=result[1]
            self.state=GameState.over
            return result
        if len(self.board.board[self.board.board==0])==0:
            result=(1,None) #平局
            self.winner=None
            self.state=GameState.over
            return result
        result=(-1,None) #还没结束
        self.winner=None
        self.state=GameState.running
        return result
    def run(self,mode='hvh',bot1_mode='r',bot2_mode='r'):
        self.state=GameState.running
        if mode=='hvh': #人vs人
            while self.getResult()[0]==-1: #没有决出胜负
                os.system('cls')
                self.board.printBoard()
                if self.player==1:
                    s=input('X,请以空格分割坐标：') #输入“1 1”表示中心位置
                else:
                    s=input('O,请以空格分割坐标：') #输入“1 1”表示中心位置
                s=s.strip().split(" ")
                if len(s)!=2:
                    continue #输入非法就重新输入
                s=np.array(s).astype(int)
                try:
                    if self.board.board.item(tuple(s.tolist()))==0:
                        self.board.board.itemset(tuple(s.tolist()),self.player)
                    else:
                        continue #输入非法就重新输入
                except IndexError:
                    continue
                self.player=0-self.player
            os.system('cls')
            self.board.printBoard()
            if self.winner==None:
                print("平局")
            else:
                if self.winner==1:
                    self.winner='X'
                    print("X wins!")
                else:
                    self.winner='O'
                    print("O wins!")
        elif mode=='hvb': #人vs机器
            bot=Agent(self,player_o,mode=bot2_mode)
            while self.getResult()[0]==-1:
                #os.system('cls')
                self.board.printBoard()
                time.sleep(.3)
                if self.player==player_x:
                    move=input('X,请以空格分割坐标：')
                    move=move.strip().split(" ")
                    if len(move)!=2:
                        continue #输入非法就重新输入
                    move=np.array(move).astype(int)
                    move=tuple(move.tolist())
                    if not self.isLegalMove(move):
                        continue
                    else:
                        self.applyMove(move)
                else:
                    move=bot.chooseMove()
                    if not self.isLegalMove(move):
                        continue
                    else:
                        self.applyMove(move)
            #os.system('cls')
            self.board.printBoard()
            if self.winner==None:
                print("平局")
            else:
                if self.winner==player_x:
                    self.winner='X'
                    print("X wins!")
                else:
                    self.winner='O'
                    print("O wins!")
        elif mode=='bvh': #机器vs人
            bot=Agent(self,player_x,mode=bot1_mode)
            while self.getResult()[0]==-1:
                os.system('cls')
                self.board.printBoard()
                time.sleep(.3)
                if self.player==player_o:
                    move=input('X,请以空格分割坐标：')
                    move=move.strip().split(" ")
                    if len(move)!=2:
                        continue #输入非法就重新输入
                    move=np.array(move).astype(int)
                    move=tuple(move.tolist())
                    if not self.isLegalMove(move):
                        continue
                    else:
                        self.applyMove(move)
                else:
                    move=bot.chooseMove()
                    if not self.isLegalMove(move):
                        continue
                    else:
                        self.applyMove(move)
            os.system('cls')
            self.board.printBoard()
            if self.winner==None:
                print("平局")
            else:
                if self.winner==player_x:
                    self.winner='X'
                    print("X wins!")
                else:
                    self.winner='O'
                    print("O wins!")
        elif mode=='bvb': #机器vs机器
            bot1=Agent(self,player_x,mode=bot1_mode)
            bot2=Agent(self,player_o,mode=bot2_mode)
            while self.getResult()[0]==-1:
                os.system('cls')
                self.board.printBoard()
                time.sleep(.3)
                if self.player==player_x:
                    move=bot1.chooseMove()
                    if not self.isLegalMove(move):
                        continue
                    else:
                        self.applyMove(move)
                else:
                    move=bot2.chooseMove()
                    if not self.isLegalMove(move):
                        continue
                    else:
                        self.applyMove(move)
            os.system('cls')
            self.board.printBoard()
            if self.winner==None:
                print("平局")
            else:
                if self.winner==player_x:
                    self.winner='X'
                    print("X wins!")
                else:
                    self.winner='O'
                    print("O wins!")
        else:
            pass

    def applyMove(self,move):
        self.board.board.itemset(move,self.player)
        self.player=0-self.player
        self.last_move=move #井字棋由于没有弃权步，所以这里可以直接记录，不用关心谁执行

    def simuApplyMove(self,move):
        new_game=copy.deepcopy(self)
        new_game.applyMove(move)
        new_game.getResult()
        return new_game

    def isLegalMove(self,move):
        for i in range(2):  #不要超过棋盘大小3*3
            if move[i]>2 or move[i]<0:
                return False
        if self.board.board.item(move)!=0:
            return False
        return True

    def getLegalMoves(self):
        [x,y]=np.where(self.board.board==0)
        return list(zip(x,y))

def bestResultForOP(game): #计算对手的最好结果
    if game.state==GameState.over:
        if game.winner==game.player:
            return GameResult.win
        elif game.winner==None:
            return GameResult.draw
        else:
            return GameResult.loss
    best_so_far=GameResult.loss
    for move in game.getLegalMoves():
        #print("DDD",game.player)
        new_game=game.simuApplyMove(move)
        #print("CCC",new_game.player)
        op_best_outcome=bestResultForOP(new_game)
        #print(move,new_game.player,op_best_outcome)
        my_best_outcome=reverse_bestResultForOP(op_best_outcome)
        if best_so_far.value < my_best_outcome.value:
            best_so_far=my_best_outcome
        if best_so_far==GameResult.win: #为了减少循环量
            break
    return best_so_far


def reverse_bestResultForOP(outcome):
    if outcome==GameResult.win:
        return GameResult.loss
    elif outcome==GameResult.loss:
        return GameResult.win
    else:
        return GameResult.draw


def alpha_beta_prune(game, max_depth,best_o,best_x,evl_fn): #这个函数是可以通用的，不只是井字棋，象棋围棋都可以
    if game.state==GameState.over:
        if game.winner==game.player:
            return maxValue
        elif game.winner==None:
            return 0
        else:
            return minValue

    if max_depth == 0:
        return evl_fn(game)

    best_so_far = minValue
    for move in game.getLegalMoves():
        next_game = game.simuApplyMove(move)
        op_best_result = alpha_beta_prune(
            next_game, max_depth - 1,
            best_o, best_x,
            evl_fn)
        my_result = -1 * op_best_result
        if my_result > best_so_far:
            best_so_far = my_result

        if game.player == player_o:
            if best_so_far > best_o:
                best_o = best_so_far
            outcome_for_x = -1 * best_so_far
            if outcome_for_x < best_x:
                break
        elif game.player == player_x:
            if best_so_far > best_x:
                best_x = best_so_far
            outcome_for_o = -1 * best_so_far
            if outcome_for_o < best_o:
                break

    return best_so_far


def getResult(board): #重写一遍，用于easySimuGame判断游戏结果
		table=np.array([
		    [
		        [1,1,1],
		        [0,0,0],
		        [0,0,0],
		    ],
		    [
		        [0,0,0],
		        [1,1,1],
		        [0,0,0],
		    ],
		    [
		        [0,0,0],
		        [0,0,0],
		        [1,1,1],
		    ],
		    [
		        [1,0,0],
		        [1,0,0],
		        [1,0,0],
		    ],
		    [
		        [0,1,0],
		        [0,1,0],
		        [0,1,0],
		    ],
		    [
		        [0,0,1],
		        [0,0,1],
		        [0,0,1],
		    ],
		    [
		        [1,0,0],
		        [0,1,0],
		        [0,0,1],
		    ],
		    [
		        [0,0,1],
		        [0,1,0],
		        [1,0,0],
		    ],
		])
		result_=np.sum(table*board,axis=(1,2))
		x,y=np.where(board==0)
		if result_.max()==3:
				result=(0,1) #(有胜负，谁)
		elif result_.min()==-3:
				result=(0,-1)
		elif not list(zip(x,y)): #平局
				result=(1,None)
		else: #游戏还没结束
				result=(-1,None)
		return result




def easySimuGame(board,start_player):
		move_records=[] #记录模拟的所有步骤
		player=start_player
		while getResult(board) == (-1,None):
				[x,y]=np.where(board==0)
				move=random.choice(list(zip(x,y)))
				move_records.append((move,player))
				board.itemset(move,player)
				player=-1*player #简易版的player.other

		if getResult(board)==(1,None): #平局
				return (move_records,GameResult.draw)
		else: #有胜负
				if getResult(board)[1]==start_player:
						return (move_records,GameResult.win)
				else:
						return (move_records,GameResult.loss)

def evl_game(game): #价值评估站在当前player的角度来做的
    if getResult(game.board.board)[1] != None: #有胜负，player_x胜
        if game.player == getResult(game.board.board) == (0,1)[1]:
            return 1
        else:
            return -1
    else:
        return 0



class tree:
		def __init__(self):
				self.node_name=0
				self.root =Node(str(self.node_name),move=None,loss=0,win=0,draw=0,player=None) #永远指向根节点
				self.tree_root =self.root #用来指向当前节点
		def getNodeLeaves(self,node_start):
				return [node for node in LevelOrderIter(node_start, filter_=lambda n: n is not node_start,maxlevel=2)]
		def findNextNodeByMove(self,node_start,move):
				return search.find(node_start, filter_=lambda n: n is not node_start and n.move==move,maxlevel=2)
		def updateLeaf(self,node_start,move_record,result):
				move,player=move_record
				loss=0
				win=0
				draw=0
				find_node=search.find(node_start, filter_=lambda n: n is not node_start and n.move==move,maxlevel=2)
				if find_node==None:
						if result==GameResult.win:
								win+=1
						elif result==GameResult.loss:
								loss+=1
						else:
								draw+=1
						self.node_name+=1
						new_node=Node(str(self.node_name), parent=node_start,move=move,loss=loss,win=win,draw=draw,player=player)
						return new_node
				else:
						loss=find_node.loss
						win=find_node.win
						draw=find_node.draw
						if result==GameResult.win:
								win+=1
						elif result==GameResult.loss:
								loss+=1
						else:
								draw+=1
						find_node.loss=loss
						find_node.win=win
						find_node.draw=draw
						return find_node

class Agent:
    def __init__(self,game,player,mode='r'):
        self.game=game #numpy数组
        self.player=player
        self.mode=mode
        self.tree=tree()

    def chooseMove(self): #只要调用这一步，说明还没下完，调用这一步前已经判断过游戏有没有结束
        if self.mode=='r': #r for random
            moves=self.game.getLegalMoves()
            return random.choice(moves)
        if self.mode=='ai': #ai for 穷举
            moves=self.game.getLegalMoves()
            win_moves=[]
            loss_moves=[]
            draw_moves=[]
            for move in moves:
                new_game=self.game.simuApplyMove(move)
                op_best_outcome=bestResultForOP(new_game)   #接下去由于是对方下棋，所以从对方角度开始评估
                my_best_outcome=reverse_bestResultForOP(op_best_outcome)
                if my_best_outcome==GameResult.win:
                    win_moves.append(move)
                elif my_best_outcome==GameResult.loss:
                    loss_moves.append(move)
                else:
                    draw_moves.append(move)
                #break
            if win_moves:
                #print("win")
                return random.choice(win_moves)
            elif draw_moves:
                #print("draw")
                return random.choice(draw_moves)
            else:
                #print("loss")
                return random.choice(loss_moves)
        if self.mode=='ab': #ab as alpha-beta
            moves=self.game.getLegalMoves()
            best_moves=[]
            best_score=None #以最悲观的价值来初始化才有进步的空间
            best_o=minValue
            best_x=minValue
            for move in moves:
                new_game=self.game.simuApplyMove(move)
                op_best_outcome = alpha_beta_prune(new_game, max_depth,best_o,best_x,evl_game)
                my_best_outcome = -1 * op_best_outcome
                if (not best_moves) or my_best_outcome > best_score:
                    best_moves = [move]
                    best_score = my_best_outcome
                    if self.game.player == player_x:
                        best_x = best_score
                    elif self.game.player == player_o:
                        best_o = best_score
                elif my_best_outcome == best_score:
                    best_moves.append(move)
            return random.choice(best_moves)

        if self.mode=='mt': #蒙特卡洛树搜索方法
        		try_times=1000 #蒙特卡洛循环多少次
        		#根据当前局面剪出新的树枝
        		if self.game.last_move is not None:
        				node_tmp=self.tree.findNextNodeByMove(self.tree.tree_root,self.game.last_move) #查找对方走的那步是不是在之前的树里有
        				if node_tmp==None: #如果没有就新建一个树叶
        						self.tree.node_name+=1
        						self.tree.tree_root=Node(str(self.tree.node_name),parent=self.tree.tree_root,move=self.game.last_move,loss=0,win=0,draw=0,player=-1*self.player)
        				else:
        						self.tree.tree_root=node_tmp
        		node_point=self.tree.tree_root
        		#模拟棋局
        		for i in range(try_times):
        				board_=copy.copy(self.game.board.board)
        				node_start=node_point
        				move_records,game_result=easySimuGame(board_,self.player)
        				for move in move_records:
        						node_start=self.tree.updateLeaf(node_start,move,game_result)
        		all_next_leaves=self.tree.getNodeLeaves(node_point)
        		#根据模拟结果选择最优
        		all_rates=[(node.loss/(node.loss+node.win+node.draw)) for node in all_next_leaves]
        		all_rates=np.array(all_rates)
        		pick_move_index=int(random.choice(np.argwhere(all_rates==min(all_rates))))
        		self.tree.tree_root=all_next_leaves[pick_move_index] #指向新的树叶作为新的根节点
        		return all_next_leaves[pick_move_index].move










def main():
    board=Board()
    game=Game(board)
    game.run(mode='bvb',bot2_mode='ab',bot1_mode='ab')

if __name__ == '__main__':
    main()
